package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;

public class Day25 {

    /**
     * 堆大小，小于这个范围的数才视作堆的一部分
     * 存在逻辑删除的意思，如果数组中数index>heapSize 不会被视为堆的一部分
     * 如果后续拓展仿照ArrayList存储对象 ，最好把删除的数据置为空方便垃圾回收器回收
     */
    private int heapSize = 0;
    /***
     * 存储数据
     */
    private int[] heap = new int[100];

    /***
     * 打印数据 只打印小于heapSize的数据
     */
    private void print() {
        StringBuilder str = new StringBuilder();
        for (int index = 0; index < heapSize; index++) {
            str.append(heap[index]).append(" ");
        }
        System.out.println(str);
    }

    /***
     * 插入数据
     * @param num
     */
    public void add(int num) {
        //将最后的位置设置为num
        heap[heapSize] = num;
        //父节点的位置
        int father = (heapSize - 1) / 2;
        //当前数的位置
        int cur = heapSize;
        //如果当前点的值大于父亲 需要进行交换
        while (heap[cur] > heap[father]) {
            //交换
            ArrayUtils.swap(heap, cur, father);
            //位置设置为父节点位置
            cur = father;
            //重置父节点
            father = (cur - 1) / 2;
        }
        //新增数据 那么堆大小++
        heapSize++;
    }

    /***
     * 这是一个大根堆 0就是最大啦
     * @return
     */
    public int getMax() {
        return heap[0];
    }

    /****
     * 删除最大
     */
    public void removeMax() {
        //首先和堆最末尾（叶子节点）进行交换
        ArrayUtils.swap(heap, 0, heapSize);
        //堆大小缩小，所有原来的根节点位置大于等于heapSize，等于逻辑删除
        heapSize--;
        //当前需要进行调整节点的位置，
        int curIndex = 0;
        //当前需要进行调整节点的值
        int curValue = heap[curIndex];
        //左节点的下标
        int leftIndex = 1;
        //左节点值
        int leftValue = getValueIfOutSizeReturnIntMin(leftIndex);
        //右节点的下标
        int rightIndex = 2;
        //右节点值
        int rightValue = getValueIfOutSizeReturnIntMin(rightIndex);
        //只要小于任意一个节点我们就需要交换
        while (curValue < leftValue || curValue < rightValue) {
            //先默认左节点的值大 取左节点的节点
            int tempIndex = leftIndex;
            //左节点值小于右节点值
            if (leftValue < rightValue) {
                //我们需要和右节点进行交换
                tempIndex = rightIndex;
            }
            //和较大节点交换
            ArrayUtils.swap(heap, tempIndex, curIndex);
            //当前位置修改 重置左右节点值，进行下一轮循环
            curIndex = tempIndex;
            curValue = heap[curIndex];
            leftIndex = 2 * curIndex + 1;
            rightIndex = 2 * curIndex + 2;
            leftValue = getValueIfOutSizeReturnIntMin(leftIndex);
            rightValue = getValueIfOutSizeReturnIntMin(rightIndex);
        }
    }

    /***
     * 设置一个位置的值
     * @param index
     * @param num
     */
    public void set(int index, int num) {
        heap[index] = num;
        //有父节点而且父节点的值比num小
        while (hasFather(index) && heap[(index - 1) / 2] < num) {
            //和父节点交换
            int fatherIndex = (index - 1) / 2;
            ArrayUtils.swap(heap, index, fatherIndex);
            //重置下表
            index = fatherIndex;
        }
        //有子节点
        while (hasSon(index)) {
            //左孩子
            int leftSon = 2 * index + 1;
            //右孩子
            int rightSon = 2 * index + 2;
            int leftValue = getValueIfOutSizeReturnIntMin(leftSon);
            int rightValue = getValueIfOutSizeReturnIntMin(rightSon);
            //大于左右孩子 结束
            if (heap[index] >= rightSon && heap[index] >= leftSon) {
                break;
            }
            //那个子节点的值大 取那个子节点的下表
            int tempIndex = leftValue > rightValue ? leftSon : rightSon;
            //和较大子节点进行交换
            ArrayUtils.swap(heap, index, tempIndex);
            //更新下表等待下一次循环
            index = tempIndex;
        }
    }

    private boolean hasFather(int index) {
        if (index <= 0) {
            return false;
        }
        int fatherIndex = (index - 1) / 2;
        return fatherIndex < heapSize;
    }

    private boolean hasSon(int index) {
        if (index < 0) {
            return false;
        }
        int sonIndex = 2 * index + 1;
        return sonIndex < heapSize;
    }

    private int getValueIfOutSizeReturnIntMin(int index) {
        if (index > heapSize) {
            return Integer.MIN_VALUE;
        }
        return heap[index];
    }

    public static void main(String[] args) {
        Day25 heap = new Day25();
        heap.add(1);
        heap.add(2);
        heap.add(3);
        heap.print();
        heap.add(2);
        heap.print();
        heap.add(4);
        heap.print();
        heap.removeMax();
        heap.print();
        heap.set(2, 100);
        heap.print();

    }
}
